package Data_Structure.Sort;

/**
 * @className: InsertSort
 * @author: 芃
 * @description: 直接插入排序实现
 * @date: 2023/8/20 17:18
 */
//主要思想：
// 举例：12 9 5 4 10
//i从1下标开始走，j为i-1下标
//每次都将i下标位置的元素插入到前面已经有序的数组中
//为什么i要从1下标开始走？因为我们只有一个元素的时候，默认它就是有序的

//时间复杂度：O(n^2) -》最好情况是O（N），数组已经有序时
//根据这个结论，推导出另外一个结论：对于直接插入排序来说，越有序越快
//空间复杂度：O(1) 未开辟新的内存空间
//稳定性：稳定的，可以实现为不稳定的
//怎么实现为不稳定？比较条件改为(arr[j] >= tmp)时就不稳定了
public class InsertSort {
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else {
                    //只要j回退的时候遇到了比tmp小的就结束比较，因为前面的顺序已经有序，只是在给tmp找合适的位置
                    //arr[j+1] = tmp;
                    break;
                }
            }
            //j回退到了小于0的下标
            arr[j+1] = tmp;
        }
    }
}
